package graph;

import java.util.ArrayList;

public class GraphByNode {
    static class Node{
        public int src;//起始位置
        public int dest;//目标位置
        public int weight;//权重
        public Node next;

        public Node(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }
    public char[] arrV;
    public ArrayList<Node> edgList;//存储边
    public boolean isDirect;//是否有向

    public GraphByNode(int size, boolean isDirect) {
        this.arrV = new char[size];
        edgList=new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            edgList.add(null);
        }
        this.isDirect=isDirect;
    }
    //初始化顶点数组
    public void initArrV(char[] arr) {
        for (int i = 0; i < arrV.length; i++) {
            arrV[i] = arr[i];
        }
    }
    //添加边
    //srcV-起点 destV-终点 weight-权值
    public void addEdge(char srcV,char destV,int weight){
        int srcIndex=getIndexOfV(srcV);
        int destIndex=getIndexOfV(destV);
        addEdgeChild(srcIndex, destIndex, weight);
        //无向图需要添加两条边
        if(!isDirect){
            addEdgeChild(destIndex, srcIndex, weight);
        }
    }
    private void addEdgeChild(int srcIndex,int destIndex,int weight){
        //这里拿到的是头节点
        Node cur=edgList.get(srcIndex);
        while(cur!=null) {
            if (cur.dest == destIndex) {
                return;
            }
            cur = cur.next;
        }
        //说明之前没有存储过这条边
        //头插法
        Node node=new Node(srcIndex,destIndex,weight);
        node.next=edgList.get(srcIndex);
        edgList.set(srcIndex,node);
    }
    //获取顶点v的下标
    private int getIndexOfV(char v){
        for (int i = 0; i < arrV.length; i++) {
            if(arrV[i]==v){
                return i;
            }
        }
        return -1;
    }
    //获取顶点的度
    public int getDevOfV(char v) {
        int count = 0;
        int srcIndex=getIndexOfV(v);
        Node cur=edgList.get(srcIndex);
        //无向图
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        //有向图
        if(isDirect){
            int destIndex=srcIndex;
            for (int i = 0; i < arrV.length; i++) {
                if(i==destIndex){
                    continue;
                }else{
                    Node pCur=edgList.get(i);
                    while (pCur != null) {
                        if(pCur.dest==destIndex){
                            count++;
                        }
                        pCur = pCur.next;
                    }
                }
            }
        }
        return count;
    }

        //打印
    public void printGraph() {
        for (int i = 0; i < arrV.length; i++) {
            System.out.print(arrV[i]+"-> ");
            Node cur = edgList.get(i);
            while(cur!=null){
                System.out.print(arrV[cur.dest]+" ");
                cur=cur.next;
            }
            System.out.println();
        }
    }
}
